package kyssion.leetcode.num51_100;

public class code97_交错字符串 {

    public static void main(String[] args) {
        System.out.println(new code97_交错字符串()
                .isInterleave("ab",
                        "bc",
                        "babc"));
    }

    /**
     * dp 公式 dp[c][a][b] = dp[c-1][a-1][b]||dp[c-1][a][b-1]
     *
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.equals("") || s2.equals("")) {
            return s3.equals(s1) || s3.equals(s2);
        }

        if (s3.length() != s1.length() + s2.length()) {
            return false;
        }
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        dp[0][0] = true;
        for (int a = 1; a <= s3.length(); a++) {
            int l2 = a <= s2.length() ? a : s2.length();
            int l1 = a - l2;
            while (l1 <= a && l1 <= c1.length) {
                if (l1 > 0 && c1[l1 - 1] == c3[a - 1]) {
                    dp[l1][l2] = dp[l1 - 1][l2];
                }
                if (l2 > 0 && c2[l2 - 1] == c3[a - 1]) {
                    dp[l1][l2] = dp[l1][l2 - 1] || dp[l1][l2];
                }
                l1++;
                l2--;
            }
        }
        return dp[s1.length()][s2.length()];
    }

    /**
     * 递推公式另一种变形
     *
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public boolean isInterleave3(String s1, String s2, String s3) {
        int l1 = s1.length(), l2 = s2.length(), l3 = s3.length();
        if (l1 + l2 != l3) {
            return false;
        }
        boolean[][] dp = new boolean[l1 + 1][l2 + 1];
        dp[0][0] = true;
        for (int i = 1; i <= l1; i++) {
            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        }
        for (int j = 1; j <= l2; j++) {
            dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                        || (dp[i][j - 1] && s3.charAt(i - 1 + j) == s2.charAt(j - 1));
            }
        }
        return dp[l1][l2];
    }

    /**
     * 深度搜索+dp 速度太慢了
     *
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public boolean isInterleave2(String s1, String s2, String s3) {
        if (s1.equals("") || s2.equals("")) {
            return s3.equals(s1) || s3.equals(s2);
        }

        if (s3.length() != s1.length() + s2.length()) {
            return false;
        }

        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        char[] chars3 = s3.toCharArray();
        ansOne(1, chars1, 0, chars2, 1, chars3, dp);
        ansTwo(0, chars1, 1, chars2, 1, chars3, dp);
        return dp[chars1.length][chars2.length];
    }

    private void ansOne(int i, char[] chars1, int j, char[] chars2, int p, char[] chars3, boolean[][] dp) {
        if (i <= chars1.length && p <= chars3.length && chars1[i - 1] == chars3[p - 1]) {
            dp[i][j] = true;
            ansOne(i + 1, chars1, j, chars2, p + 1, chars3, dp);
            ansTwo(i, chars1, j + 1, chars2, p + 1, chars3, dp);
        }
    }

    private void ansTwo(int i, char[] chars1, int j, char[] chars2, int p, char[] chars3, boolean[][] dp) {
        if (j <= chars2.length && p <= chars3.length && chars2[j - 1] == chars3[p - 1]) {
            dp[i][j] = true;
            ansOne(i + 1, chars1, j, chars2, p + 1, chars3, dp);
            ansTwo(i, chars1, j + 1, chars2, p + 1, chars3, dp);
        }
    }


    public boolean isInterleave4(String s1, String s2, String s3) {
        char[] c1 = s1.toCharArray(), c2 = s2.toCharArray(), c3 = s3.toCharArray();
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) return false;
        return dfs(c1, c2, c3, 0, 0, 0, new boolean[m + 1][n + 1]);
    }

    public boolean dfs(char[] c1, char[] c2, char[] c3, int i, int j, int k, boolean[][] invalid) {
        if (invalid[i][j]) return false;
        if (k == c3.length) return true;
        boolean valid =
                i < c1.length && c1[i] == c3[k] && dfs(c1, c2, c3, i + 1, j, k + 1, invalid) ||
                        j < c2.length && c2[j] == c3[k] && dfs(c1, c2, c3, i, j + 1, k + 1, invalid);
        if (!valid) invalid[i][j] = true;
        return valid;
    }

}
